Wash[贪心]
Wash[贪心]
hdu 6000
集训时的一道题，做的时候靠蒙找到了最优情况，实际上是可以严格的证明的。
题解
较为复杂的贪心算法，其难度也主要是集中在选择其贪心策略的问题上，或者说是对贪心策略正确性的证明上。所以我们集中来看这道题的贪心策略。
题目给出了一个w[]数组和一个d[]数组，要求其中各取L个数，然后令其$ max( w_i + d_j )\(。所以我们的目标是找到一种组合情况，使得\)w_i+d_j$的最大值最小。
首先，对于从w[]和d[]数组中取出的L个数，我们肯定是要取出最小的L个。然后，我们可以粗略的看出，当我们的w[]越小时，我们取的d[]越大越好。因此，我们可以对w[]从小到大排序，d[]从大到小排序，然后每个各自相加即可。
我们可以较为严格的证明一下: 假设我们已经按照如上顺序放好。那么，我们对于$ i,j (i < j)\(, 其一定满足\) w_i w_j , d_i d_j $，所以当我们调换顺序时，这两个数中的最大值一定会大于等于原来的最大值。并且这两个数的调换不会对其他数造成影响，所以我们明显不能调换，原来的顺序即使最佳情况。
此外，还需要注意的一点: 对于此题，由于洗衣机和干洗机都可以重复使用，所以我们刚开始需要从中取出的L个数并不仅仅是排序后取前L个，而是需要考虑一个机子使用多次的情况，所以这里最好用优先队列，一个个的取出，然后再将下一次能够使用的时间放入。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct Node
{
truelong long x,base;
trueNode(long long x,long long base):x(x),base(base) {}
trueconst bool operator < (const Node &tmp) const{
truetruereturn x > tmp.x;
true}
};
long long t1[1000100],t2[1000100];
priority_queue<Node> q1,q2;
int main()
{
trueint T;
truescanf("%d",&T);
truefor (int cas = 1; cas<=T; cas++)
true{
truetrueq1 = priority_queue<Node>();
truetrueq2 = priority_queue<Node>();
truetrueint l,n,m;
truetruescanf("%d%d%d",&l,&n,&m);
truetruefor (int i = 1; i<=n; i++)
truetrue{
truetruetruelong long x;
truetruetruescanf("%lld",&x);
truetruetrueq1.push(Node(x,x));
truetrue}
truetruefor (int i = 1; i<=m; i++)
truetrue{
truetruetruelong long x;
truetruetruescanf("%lld",&x);
truetruetrueq2.push(Node(x,x));
truetrue}
truetruefor (int i = 1; i<=l; i++)
truetrue{
truetruetrueNode t = q1.top();
truetruetrueq1.pop();
truetruetruet1[i] = t.x;
truetruetruet.x += t.base;
truetruetrueq1.push(t);
truetrue}
truetruefor (int i = 1; i<=l; i++)
truetrue{
truetruetrueNode t = q2.top();
truetruetrueq2.pop();
truetruetruet2[i] = t.x;
truetruetruet.x += t.base;
truetruetrueq2.push(t);
truetrue}
truetruelong long ans = 0;
truetruefor (int i = 1; i<=l; i++)
truetruetrueans = max(ans, t1[i] + t2[l-i+1]);
truetrueprintf("Case #%d: %lld\n",cas,ans);
true}
}
|